#include "uni_set.h"

UnionSet::UnionSet(int n)
{
	for(int i=0;i<n;i++)
	{
		par[i]=i;
		rank[i]=0;
	}
}

int 
UnionSet::find(int x)
{
	if(par[x]==x)
		return x;
	else
		return par[x]=find(par[x]);
}

void 
UnionSet::unite(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y) return;
	if(rank[x]<rank[y])
	{
		par[x]=y;
	}
	else
	{
		par[y]=x;
		if(rank[x]==rank[y]) rank[x]++;
	}
}

bool 
UnionSet::same(int x,int y)
{
	return find(x)==find(y);
}
